package com.lc.w455;

import java.io.IOException;
import java.util.*;

public class d {

    public static void main(String[] args) throws IOException {

    }

    // dis 表示距离
    // stage 表示阶段
    // mask 表示 没有过河的人
    // direction 0 表示一群人要过河的状态
    //           1 表示一个人要回来的状态
    private record Tuple(double dis, int stage, int mask, int direction) {

    }

    public double minTime(int n, int k, int m, int[] time, double[] mul) {
        int u = 1 << n;
        // 预处理每个 time 子集的最大值
        int[] maxTime = new int[u];
        for (int i = 0; i < n; i++) {
            int highBit = 1 << i;
            for (int mask = 0; mask < highBit; mask++) {
                maxTime[highBit | mask] = Math.max(maxTime[mask], time[i]);
            }
        }

        // 把 maxTime 中的大小大于 k 的集合改为 inf
        for (int i = 0; i < u; i++) {
            if (Integer.bitCount(i) > k) {
                maxTime[i] = Integer.MAX_VALUE;
            }
        }

        double[][][] dis = new double[m][u][2];
        for (double[][] mat : dis) {
            for (double[] row : mat) {
                Arrays.fill(row, Double.MAX_VALUE);
            }
        }

        PriorityQueue<Tuple> h = new PriorityQueue<>(Comparator.comparingDouble(t -> t.dis));
        push(0, 0, u - 1, 0, dis, h);

        while (!h.isEmpty()) {
            Tuple top = h.poll();
            double d = top.dis;
            int stage = top.stage;
            // 剩余没有过河的人
            int left = top.mask;
            int direction = top.direction;
            if (left == 0) {
                return d;
            }
            if (d > dis[stage][left][direction]) {
                continue;
            }
            if (direction == 0) {
                // 枚举 sub 这群人坐一艘船过河
                for (int sub = left; sub > 0; sub = (sub - 1) & left) {
                    if (maxTime[sub] != Integer.MAX_VALUE) {
                        double cost = maxTime[sub] * mul[stage];
                        push(d + cost, (stage + (int) cost) % m, left ^ sub, 1, dis, h);
                    }
                }
            } else {
                // 枚举回来的人
                for (int s = (u - 1) ^ left, lb = 0; s > 0; s ^= lb) {
                    // 枚举在s中的所有人
                    lb = s & -s;
                    double cost = maxTime[lb] * mul[stage];
                    push(d + cost, (stage + (int) cost) % m, left ^ lb, 0, dis, h);
                }
            }
        }
        return -1;
    }

    public void push(double d, int stage, int mask, int direction, double[][][] dis, PriorityQueue<Tuple> pq) {
        if (d < dis[stage][mask][direction]) {
            dis[stage][mask][direction] = d;
            pq.add(new Tuple(d, stage, mask, direction));
        }
    }
}
